解答1[Java]:
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < nums1.length; i++) {
if (map.containsKey(nums1[i]))
map.put(nums1[i], map.get(nums1[i]) + 1);
else
map.put(nums1[i], 1);
}
for (int i = 0; i < nums2.length; i++) {
if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
result.add(nums2[i]);
map.put(nums2[i], map.get(nums2[i]) - 1);
}
}
int[] r = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
r[i] = result.get(i);
}
return r;
}
}
复杂度分析
HashMap 的 get()
时间复杂度为 。
解答2[Java]:
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
List<Integer> intersection = new ArrayList<>();
Arrays.sort(nums1);
Arrays.sort(nums2);
int i=0;
int j = 0;
while(i < nums1.length && j < nums2.length){
if(nums1[i] == nums2[j]){
intersection.add(nums2[j]);
i++;
j++;
}else if(nums1[i] > nums2[j]){
j++;
}else{
//nums[i] < nums[j]
i++;
}
}
int[] res = new int[intersection.size()];
for(int k = 0; k < intersection.size();k++){
res[k] = intersection.get(k);
}
return res;
}
}
思路
先对数组进行排序,然后两个数组分别设一个指针,分别比较。